/****************************************	
 *  Submitted by:				        *
 *  Michael Fildstein, ID: 309161594    *
 *	Tomer Ben Rachel, ID: 021982475	 	*
 *       								*
 ***************************************/


/*This program builds up in stages the algorithm for the counting sort.
First, with the use of the function isSorted, we check to see if an array is sorted in an ascending order
Next, the function sameNumbers compares two arrays to see if they both have exactly the same numbers
Finally, we implement the counting sort algorithm.
*/ 
 
 

import java.util.Random;


public class CountingSort {

	//The function isSorted returns true iff the array is sorted in an ascending order
	public static boolean isSorted(int[] a){
		boolean ans = true;
		if(a==null || a.length<=1) return true;         //an array equal to null, is sorted in an ascending order by default
    if(ans)				 
      {for (int i = 0 ; i < a.length - 1 && ans ; i++)  //A for loop that checks if the following number 
				{if (!(a[i] <= a[i+1]))                         //is bigger than the current number
					{ans = false;				         
				  }
			  }
			}	
		return ans;
		
		
	}
	
	//The function sameNumbers returns true iff a1 and a2 contain exactly the same numbers
	//note - [1,2,2] does NOT contain the same numbers as [1,1,2]
	public static boolean sameNumbers(int[] a1, int[] a2){
		boolean ans = false; 
    if(a1==null && a2==null || a1.length==0 && a2.length==0) return true; 
    else if (a1!=null && a2!=null && a1.length == a2.length) //Makes sure that the input is correct		
      {ans = true;		                               							
			 int[] auxiliaryArray = new int[a1.length];       //An array of integer data type used to store
			 for (int i = 0 ; i < a1.length && ans ; i++)     //the numbers from the first array in order to compare
				{auxiliaryArray[i] = a1[i];                     //them with the second array
				 
				//checks how many times a certain number shows up in both arrays.
				 if (!((repeatInArray(a1, auxiliaryArray[i])) == (repeatInArray(a2, auxiliaryArray[i]))))
					{ans = false;																		  
					}
				}
			
			}
		return ans;
		
	}
	
	//The function repeatInArray checks how many times a certain number appears in an array
	//and returns that number
	public static int repeatInArray (int[] array , int number){  
		int ans = 0;
		for (int i = 0 ; i < array.length ; i++)
			{if (array[i] == number )
				{ans = ans + 1;    //increasing the counter each time the number appears
				}
			}
		return ans;
		
	}
	
	//The function findMax finds the maximum value in an array of ints
	//and returns the maximum value
	public static int findMax (int [] array ){	
		int ans = 0;
		for (int i = 0 ; i < array.length ; i++)
			{if (array[i] > ans)
				{ans = array[i];
				}
			}	
		return ans;
	}
	
	
	
	//The function countingSum sums up all the values in an array until a given index
	//And returns that sum
	public static int countingSum (int[] array ,int index){ 
		int ans = 0;
		for (int i = index ; i >= 0 ; i--)
			{ans = ans + array[i];          //Adding the values
			}
		return ans;
	}
	
	
	
	//sorts the input array using counting sort (array must contain only natural numbers):
	//1. Find the maximal number in the array - max
	//2. Initialize the counting array of size max + 1
	//3. Go over the input array and count in the counting array all occurrences of each number
	//4. Sum the counting array such that each entry will contain the sum of all entries smaller than it
	//5. The counting array now contains the location of the last item of each type
	//6. Go over the unsorted array and copy each number into the sorted array using the counting array
	public static int[] countingSort(int[] aiUnsorted){
		boolean legal=true;
		int[] sortedArray = new int[aiUnsorted.length];
		if(aiUnsorted==null || notNatural(aiUnsorted)){
			legal=false;  //If the input is incorrect(null array/contains numbers that are not natural
		}else if(aiUnsorted.length==0){
			return aiUnsorted;
		}
		if(legal){
			int[] countingArray = new int[findMax(aiUnsorted) + 1]; 	//Determining the maximum value and creating an array with the maximum value length.
																	
			for (int i = 0 ; i < countingArray.length ; i++)			//Counting how many times a number repeats in the array and 
				{countingArray[i] = repeatInArray(aiUnsorted, i);		//placing that number in the array cell of the number's index.
				}	
			for (int i = countingArray.length - 1 ; i > 0 ; i--)
				{countingArray[i] = countingSum(countingArray, i) - 1;  //Summing up 
				}
			for (int i = 0 ; i < aiUnsorted.length ; i++)
				{sortedArray[countingArray[aiUnsorted[i]]] = aiUnsorted[i];
				 countingArray[aiUnsorted[i]] = countingArray[aiUnsorted[i]] - 1; 
				}
			}
		else sortedArray=null;	
	return sortedArray;
		
	}
	
	

	//The function notNatural checks to see if the array contains numbers that are not natural
	//Returns true if there ar numbers that are not natural, otherwise, false
	public static boolean notNatural(int[] aiUnsorted){
		boolean ans = false;
		for(int i=0;i<aiUnsorted.length && !ans;i=i+1)
			{if(aiUnsorted[i]<0) ans=true;
			}
		return ans;
	}	
	
	
	public static void main(String[] args) {
		
		// for inSort testing
		int[] testArreySorted = {2,3,4,5,6,7,8};
		int[] testArreyUnsorted2 = {2,3,4,5,6,7,8,1};
		int[] testArreyUnsorted = {8,7,6,5,0,0,7};
		int[] testArreyZeros = new int[20];
		int[] testArrayNull = null;
		int[] testArrayZero = new int[0];
		
		System.out.println("****************  Testing the 'isSorted' Function ****************" );
		System.out.println("Test 1:This should be true:"+ isSorted(testArreySorted));
		System.out.println("Test 2:This should be false:"+ isSorted(testArreyUnsorted2));
		System.out.println("Test 3:This should be false:"+ isSorted(testArreyUnsorted));
		System.out.println("Test 4:This should be true:"+ isSorted(testArreyZeros));
		System.out.println("Test 5:This should be true:"+ isSorted(testArrayNull));
				System.out.println(" Test 6:This should be true:"+ isSorted(testArrayZero));
		System.out.println("****************  End of Test ****************" );
		
		// for sameNumbers testing
		
		int[] arrey1 = {1,1,2};
		int[] arrey2 = {1,2,1};
		int[] arrey3 = {1,2,2};
		int[] arrey4 = {2,2};
		int[] array5 = null;
		int[] array6 = null;
		int[] array7 = {0,0,0,0};
		int[] array8 = {0,0,0};
		int[] array9 = {0,0,0,0};
		int[] array10 = new int[0];
		
		System.out.println("");
		System.out.println("****************  Testing the 'sameNumbers' Function ****************" );
		System.out.println("Test 7: This should be true:"+ sameNumbers(arrey1, arrey2));
		System.out.println("Test 8:This should be false:"+ sameNumbers(arrey1, arrey3));
		System.out.println("Test 9:This should be false:"+ sameNumbers(arrey1, arrey4));
		System.out.println("Test 10:This should be true:"+ sameNumbers(array5, array6));
		System.out.println("Test 11:This should be false:"+ sameNumbers(array7, array8));
		System.out.println("Test 12:This should be true:"+ sameNumbers(array7, array9));
		System.out.println("Test 13:This should be false:"+ sameNumbers(arrey1, array10));
		System.out.println("****************  End of Test ****************" );
		
		// for findMax testing
		System.out.println("");
		System.out.println("****************  Testing the 'findMax' Function ****************" );
		System.out.println("Test 14:This should be 2:"+ findMax(arrey1));
		System.out.println("Test 15:This should be 2:"+ findMax(arrey2));
		System.out.println("Test 16:This should be 2:"+ findMax(arrey3));
		System.out.println("Test 17:This should be 2:"+ findMax(arrey4));
		System.out.println("Test 18:This should be 0:"+ findMax(testArreyZeros));
		System.out.println("Test 20:This should be 8:"+ findMax(testArreyUnsorted));
		System.out.println("Test 21:This should be 8:"+ findMax(testArreyUnsorted2));
		System.out.println("Test 22:This should be 8:"+ findMax(testArreySorted));
//		System.out.println("Test 22:This should be 8:"+ findMax(array5));
		
		
		
		System.out.println("****************  End of Test ****************" );
		
		
		
		int iLength = 100, iMax = 20;
		Random rnd = new Random();
		int[] aiUnsorted = new int[iLength], aiSorted = null;
		int i = 0;
		for( i = 0 ; i < aiUnsorted.length ; i++ ){
			aiUnsorted[i] = rnd.nextInt(iMax);
			}
		aiSorted = countingSort(aiUnsorted);
		
		if(isSorted(aiSorted) && sameNumbers(aiUnsorted, aiSorted))
			System.out.println("Success");
		else
			System.out.println("Failed"); 
	} 

}
